/**
 * 有序链表转化为二叉搜索树
 *
 * 给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树。
 *
 * 示例 1:
 * 输入: head = [-10,-3,0,5,9]
 * 输出: [0,-3,9,-10,null,5]
 * 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
 *
 * 示例 2:
 * 输入: head = []
 * 输出: []
 *
 * 提示 :
 * head 中的节点数在[0, 2 * 104] 范围内
 * -105 <= Node.val <= 105
 */

/**
 * 这一题和上一题的思路是一样的, 就是找到中间的数, 这里我直接
 * 将链表转化为了数组, 还可以使用快慢指针的方法来寻找中间节点
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {
    public TreeNode sortedListToBST(ListNode head) {

        int n = 0;
        ListNode cur = head;

        // 求链表长度
        while (cur != null) {
            cur = cur.next;
            n++;
        }

        int[] nums = new int[n];

        cur = head;

        // 转化为有序数组
        for (int i = 0; i < n; i++) {
            nums[i] = cur.val;
            cur = cur.next;
        }

        return dfs(nums, 0, nums.length - 1);
    }

    // 递归
    public TreeNode dfs (int[] nums, int start, int end) {
        if (start > end) {
            return  null;
        }
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, start, mid - 1);
        root.right = dfs(nums, mid + 1, end);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}